#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 *给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

 

示例 1：



输入：root = [1,null,3,2,4,null,5,6]
输出：3
示例 2：



输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

class Node {
public:
    int val;
    vector<Node *> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node *> _children) {
        val = _val;
        children = _children;
    }
};

//一下子秒杀了
int maxDepth(Node *root) {
    if (!root)
        return 0;

    int max = 0;

    for (const auto &item : root->children) {
        int t = maxDepth(item);
        if (max < t)
            max = t;
    }


    return max + 1;

}

//非递归
//int minDepth(TreeNode* root) {
//    if (root == NULL) return 0;
//    int depth = 0;
//    queue<TreeNode*> que;
//    que.push(root);
//    while(!que.empty()) {
//        int size = que.size();
//        depth++; // 记录最⼩深度
//        for (int i = 0; i < size; i++) {
//            TreeNode* node = que.front();
//            que.pop();
//            if (node->left) que.push(node->left);
//            if (node->right) que.push(node->right);
//            if (!node->left && !node->right) { // 当左右孩⼦都为空的时候，说明是最低点的⼀
//
//                return depth;
//            }
//        }
//    }
//    return depth;
//}